﻿public class Solution {
    public int CombinationSum4(int[] nums, int target)
    {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int j = 0; j <= target; j++)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                if (j >= nums[i]) dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }

    public static void Main(string[] args)
    {
        int[] nums = [1, 2, 3];
        int target = 4;

        Solution solution = new Solution();
        int res = solution.CombinationSum4(nums, target);
        Console.WriteLine(res);
    }
}